This section is devoted to analyzing the run time cost for the brute force
algorithm we developed in Sec. \ref{subsec:brute-force} and for the local search and
its variants, as described in Sec. \ref{subsec:local-search}. To be able to
analyze these, we also need to analyze the run time cost for calculating the cost
of an assignment.

\subsection{Assignment Cost}
\label{subsec:assignment-cost}

Computing the cost of a current assignment is important for being able to
analyze all functions that rely on it. Our cost function $C$, as described in
Sec. \ref{subsubsec:cost}, consists of four sub-functions, which are combined in
a linear combination. We know therefore already that:

\begin{equation}
  T(C) = T(C_{1}) + T(C_{2}) + T(C_{3}) + T(C_4)
  \label{eq:cost-c}
\end{equation}

To be able to talk about out input size, we need to define variables that
describe an assignment $A$. We use the following definitions:

\begin{description}
\item[$D_{A}$] Number of departments in $A$.
\item[$S_{A}$] Number of shift-slots in $A$.
\item[$T_{A}$] Number of shift-types in $A$.
\end{description}

The first, $C_{1}$, is a simple absolute distance of the respective sum of two
arrays. The arrays are of different size, therefore we can say that the cost of
$C_{1}$ is

\begin{equation}
  T(C_{1}) = T(n + m)
  \label{eq:cost-c1}
\end{equation}

where $n$ is the size of the current assignment $A$ (i.e. $D_{A} \cdot
S_{A} \cdot T_{A}$) and $m$ the size of the given demand (analogous to $n$ but
as it is only a demand, there are no departments present). Since $S_A$ and $T_A$
are dependent on the demand, we can re-write Eq. \ref{eq:cost-c1} as:

\begin{equation}
  T(C_1) = T(D_A \cdot 2S_A \cdot 2T_A)
  \label{eq:cost-c12}
\end{equation}

Further, $C$ computes a weighted standard deviation between shift-types and
departments over a whole quarter, i.e. $C_{2}$, and over each week in the
quarter, i.e. $C_{3}$.

 We assume summing up an array of length $m$ takes $O(m)$. To calculate the standard 
deviation of a set of numbers $M$ of length $m$, three steps over $m$ are necessary: 
calculate the mean, calculate each value's square difference to the mean, calculate 
the square root of the mean of the values calculated in the step before. Therefore, 
the running time of an algorithm that calculates the standard deviation is:

\begin{eqnarray}
  T(StdDev) &=& T(mean) + T(sqDiff) + T(sqrtMean) \in O(m)
  \label{eq:cost-std-dev}
\end{eqnarray}

$C_2$ sums up the standard deviation of each type over all departments,
accessing each shift slot exactly once. Applying the run time cost as in 
Eq. \ref{eq:cost-std-dev}, we get the following run time cost for $C_2$

\begin{equation}
  T(C_2) = T(T_A \cdot 3D_A \cdot S_A)
  \label{eq:cost-c2}
\end{equation}

Analogous, the run time cost of $C_3$ is as well:

\begin{equation}
  T(C_3) = T(T_A \cdot 3D_A \cdot S_A)
  \label{eq:cost-c3}
\end{equation}

As the cost function calculating the penalty for exceeding the maximum number of
employees is a sum operation over all slots, the run time cost for $C_4$ is
merely:

\begin{equation}
  T(C_4) = T(T_A \cdot D_A \cdot S_A)
  \label{eq:cost-c4}
\end{equation}

Substituting the run time costs of all the sub-functions in Eq. \ref{eq:cost-c},
we get the final run time cost for $C$:

\begin{eqnarray}
  T(C) &=& T(C_1) + T(C_2) + T(C_3) + T(C_4) \\ 
       &=& T(D_A \cdot 2S_A \cdot 2T_A)
           + 2 \cdot T(T_A \cdot 3D_A \cdot S_A)
           + T(T_A \cdot D_A \cdot S_A) \\
       &=& T(8D_A \cdot 5S_A \cdot 5T_A) \\
       &\in& O(D_A \cdot S_A \cdot T_A) \\
       &=& O(n)
  \label{eq:cost-c-final}
\end{eqnarray}

This is a well scaling running time for the cost function we employ.

\subsection{Brute Force Algorithm}
\label{subsec:brute-force-cost}

The brute force search $BF$ we developed in Sec. \ref{subsec:brute-force} (see
Fig. \ref{fig:brute-force}) needs to consider each possible combination of shift
assignments. That means that each single shift is once combined with each
department. We use the notation introduced in
Sec. \ref{subsec:assignment-cost}. We can conclude directly from the algorithm's
outline that its running time just for the recursion is

\begin{equation}
  T(BF) = T(D^{(\sum A)})
  \label{eq:bf-1}
\end{equation}

where $(\sum A)$ is the sum of a given assignment $A$. This is already very bad as
it is exponential on input-size.

We now still need to regard the run time cost for executing the cost function for
each assignment that the function returns (see
Sec. \ref{subsec:brute-force}). First, we will black-box the analysis by
defining $C$ to be the cost function we analyzed in
Sec. \ref{subsec:assignment-cost}. Since in each recursion step an assignment is
created for each department, we extend Eq. \ref{eq:bf-1} to the following:

\begin{equation}
  T(BF) = T(D^{(\sum A)}) \cdot T(D \cdot T(C))
  \label{eq:bf-2}
\end{equation}

On substituting $T(C)$ with the actual cost from Eq. \ref{eq:cost-c-final} and
applying the two run time costs in Eq. \ref{eq:bf-2}, we get the final run time
cost for $BF$:

\begin{eqnarray}
  T(BF) &=& T(D^{(\sum A)}) \cdot T(D \cdot T(C)) \\
        &=& T(D^{(\sum A)} \cdot D \cdot T(C)) \\
        &=& T(D^{2+(\sum A)} \cdot 200 n) \\
        &\in& O(D^{3+(\sum A)} \cdot S_A \cdot T_A)
  \label{eq:bf-3}
\end{eqnarray}

This exponential run time cost is not feasible for our real input instances,
which are roughly of a size $n = 50000$. Note that in $BF$ we do not only look
at each shift-slot once but at each shift that is demanded at this slot,
i.e. the size of the value for each single shift in the demand. If we assume an
average of 8 shifts demanded per shift-slot, which is realistic, we get already
an input size of $(\sum A) = 8 \cdot 50000 = 400000$. That would result in
roughly $3,138 \cdot 10^{279595}$ operations to calculate an optimal solution.

It is therefore clear that the brute force search is not a feasible solution to
our problem.


\input{LocalSearchAnalysis.tex}

\label{subsec:local-search-cost}
